As well known, RFID (Radio Frequency Identification) is one of automatic identification methods such as a barcode, a magnetic sensor, an IC card and the like; and means a technology used for wirelessly identifying data stored in a tag's microchip by using an ultra-short wave or a long wave.
Such RFID is regarded as a substitute technology for the barcode which is currently used in distribution and circulation fields and financial services. The RFID has advantages in that there is no need of an extra identification process such as contact required in a conventional barcode method in order to achieve tag information or a reader scan in a visibility range and in that huge amounts of data can be sent.
However, since the RFID has problems with the reliability of the identified data and the delay of the technology standardization, researches on anti-collision protocols have been required to improve the characteristics of a read rate and an identification speed.
Meanwhile, there are generally two types of collisions: reader collisions and tag collisions. The reader collisions indicate that a plurality of readers requests inquiries to one tag concurrently, so it is confusing for the tag to identify the inquiries. On the contrary, the tag collisions indicate that a plurality of the tags responds to one reader's inquiry simultaneously and therefore the reader cannot identify any tag. The reader collisions can be easily solved because the readers in RFID systems detect the collisions and communicate with other readers, and therefore, the anti-collision protocols in the existing Mac layers are easily applicable to such situation. However, in case of the tag collisions, the tags which are currently used or which will be used in the large scale distribution and circulation fields are low-cost passive tags, resulting in some restrictions such as complexity of calculating, and cost increase by the memory size and the battery installation when applying usable anti-collision protocols thereto.
RFID tag anti-collision protocols proposed up to now to solve the tag collisions can be grouped into deterministic methods and probabilistic methods. The deterministic methods, which are on the basis of tree based protocols, guarantee a 100% read rate and enable low-power consumption. The tree based protocols identify tags by constructing binary trees through the use of binary bits of tag IDs and then by circulating the nodes of the trees. The tree based protocols have the characteristics capable of predicting the tag identification process. Further, the tags in the tree based protocols simultaneously start transmission with synchronous timing, and, on the other hand, the readers recognize the case that both ‘0’ and ‘1’ are included in the received values as a collision and then split the trees.
Such deterministic methods can be classified into a memory based algorithm and a memoryless based algorithm. In the memory based algorithm, which can be grouped into a splitting tree algorithm and a bit-arbitration algorithm, the reader's inquiries and the responses of the tags are stored and managed in the tag memory, thereby causing an equipment cost increase.
In contrast, in the memoryless based algorithm, the responses of the tags are not determined by the reader's previous inquiries, the tags' responses and the reader's present inquiries, but determined only by the present reader's inquiries so that the cost for the tags can be minimized. As an example, there are a binary tree working algorithm, a query tree algorithm and a collision tracking tree algorithm.
Meanwhile, the probabilistic methods are based on slotted ALOHA based protocols which do not guarantee a 100% read rate but reduce the probability of tag collisions occurring. To improve the performance, there has been suggested a frame slotted ALOHA based anti-collision algorithm wherein frames, each being formed of predetermined N slots, are used for the communications between the readers and the tags; and each tag in the interrogation zone arbitrarily selects a slot for transmitting the tag's information and loads the corresponding IDs therein.
In this algorithm, it is regarded as a collision that several tags select one slot and load each ID therein to send concurrently, but the rate of duplicated selection can be reduced by increasing the slots. However, the increase of the slots in each frame causes the increase of frame transmitting time. In spite of this contradiction, it is difficult to calculate the number of the identification objects, i.e., tags, accurately, so the appropriate number of slots required to each frame and the end point are calculated depending on the probabilistic methods. Thus, the ALOHA based anti-collision algorithm has problems in that it cannot provide the complete tag identification; and high efficiency in the tag identification cannot be expected because the slots where collisions occurred are retransmitted.
The probabilistic methods can be classified into an ID-slot algorithm and a bit-slot algorithm. The ID-slot algorithm transmits each slot where the tag ID is loaded, whereas the bit-slot algorithm transmits each slot where the information composed of specific bits for each tag is loaded to the reader and sequentially responds pursuant to the reader's call. As a representative algorithm of the ID-slot algorithm, there is an I-code algorithm, while there is an anti-collision algorithm using a bit-slot mechanism as the bit-slot algorithm.
According to the suggestion of EPC global, the binary tree working algorithm is adopted in Class 0, the query tree algorithm is adopted in Class 1, the deterministic frame slotted ALOHA algorithm is adopted in Class 1 Gen. 2 proposed to ISO/IEC 18000-6C of the International Standard Organization, and the deterministic frame slotted ALOHA algorithm being formed by adding advantages of the bit-slot algorithm to the frame slotted ALOHA based anti-collision algorithm.
In the conventional algorithms as described above, since the deterministic methods take advantages of the 100% read rate, the low-power consumption and the predictable identification process than the probabilistic methods, the deterministic methods are suitable for the reliability and for overcoming the restrictions. Accordingly, the present invention focuses on the performance enhancement of the deterministic methods for fast identification of numerous tags.
The performance of these deterministic methods has been improved from the binary tree working algorithm to the query tree algorithm and from the query tree algorithm to the collision detection algorithm. Moreover, the improvement of the algorithm for the performance enhancement is focused on how to manage the responses of the tags. In other words, in order to improve the performance of the binary tree working algorithm where only (k+1)th bit of the tag ID responds to the reader's inquiry of k bits, the query tree algorithm make the (k+1)th bit to the end bit of the tag ID respond to the reader's inquiry so one tag ID can be identified directly if there is no collision.
Furthermore, if there is a collision in the query tree algorithm, the trees are split as in the binary tree working algorithm and retransmitted after increasing one bit to the inquiry, thereby causing the waste of the time. In order to reduce the waste of the time, in the collision detection algorithm, when the reader detects the collision while observing the responses of the tags, it transmits a signal to the tags to stop the transmission and puts the received signal into the inquiries to perform identification processes.
According to such algorithms, the performance thereof can be enhanced by taking benefit while processing the responses of the tags. However, since the tag should be able to receive an ACK signal when there occurs a collision during transmission of its ID in case of a collision detection algorithm with best performance, there is a problem that the tags should be able to support both the transmission and reception at the same time, thereby making it difficult to apply to low-cost passive RFID systems. Accordingly, the query tree algorithm, adopted at present as the anti-collision protocol in EPC Class 1, may be a limitation to the tree based anti-collision protocol which can be implemented.
Moreover, in case of DFS-ALOHA (Dynamic Frame-Slotted ALOHA) adopted in EPC Class 1 Gen. 2 which is recognized as EPC Class 2, by using a technique for dynamically allocating the frame size according to the number of tags, it is prevented that the performance is rapidly degraded as the number of the tags increases.
However, this cannot solve the performance limit of ALOHA in itself, so there is still a limitation that the throughput is determined to be approximately 35%. For example, FIG. 1 describes the throughput according to the number of tags of the conventional frame slotted ALOHA with respect to the frame size; and FIG. 2 illustrates the throughput according to the number of tags of the conventional dynamic frame-slotted ALOHA.
Consequently, the RFID systems capable of fast identification are required by suggesting tag anti-collision protocols with enhanced performance capable of being implemented by mixing the characteristics of the aforementioned protocols with a limit.
In particular, one of the problems in the RFID systems is how fast to collect the tag IDs. According to the research results, the tree based and ALOHA based anti-collision protocols are somewhat effective. However, the time delay occurs in practical application due to the operation processing time in the tags and readers, and thus it is required to improve the performance of the anti-collision protocols for the faster tag identification. Furthermore, since the performance of the ALOHA based anti-collision protocols is rapidly degraded as the number of the tags increases; and a 100% read rate cannot be guaranteed by the algorithm characteristics of the ALOHA itself, the faster and more efficient tag identification capability is required in the RFID systems by improving the performance of the tree based anti-collision protocols.
Further, despite the collision detection algorithm shows the best performance among the current tree based RFID tag anti-collision algorithms, it cannot be applied to the low-cost passive RFID systems in that the tags should be able to perform both the transmission and reception at the same time in case that a collision occurs. Besides, the dynamic frame-slotted ALOHA adopted in the most recent standard ISO/IEC 18000-6C, i.e., EPC Class 1 Gen. 2 protocol, does not solve the throughput limitation of the ALOHA in itself.